// 筛法求约数个数
// 相关帖子 ：https://www.cnblogs.com/dx123/p/16712544.html
// 相关帖子 ：https://oi-wiki.org/math/number-theory/sieve/

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000001;
int cnt;
int prime[MAXN];
bool visited[MAXN];
int a[MAXN]; // a[i] 记录 i 的最小质因子的次数
int d[MAXN]; // d[i] 记录 i 的约数个数

// 试除法求约数个数
int divisors1(int n)
{
    if(n < 1) return 0;
    int ans = 1;
    for(int i = 2; i <= n / i; ++i)
    {
        if(n % i == 0)
        {
            int count = 0;
            while(n % i == 0)
            {
                ++count;
                n /= i;
            }
            ans *= (count + 1);
        }
    }
    if(n > 1) ans *= 2;
    return ans;
}

// 筛法求约数个数
void divisors2(int n)
{
    d[1] = 1;
    for(int i = 2; i <= n; ++i)
    {
        if(!visited[i])
        {
            prime[++cnt] = i;
            a[i] = 1;
            d[i] = 2;
        }
        for(int j = 1; 1LL * i * prime[j] <= n; ++j)
        {
            // prime[j] 是 m 的最小质因子
            int m = i * prime[j];
            visited[m] = true;
            if(i % prime[j] == 0)
            {
                // prime[j] 也是 i 的最小质因子
                a[m] = a[i] + 1;
                d[m] = d[i] / a[m] * (a[m] + 1);
                break;
            }
            else
            {
                a[m] = 1;
                d[m] = d[i] * 2;
            }
        }
    }
}

int main()
{
    srand(time(nullptr));
    int testTime = 100000;
    divisors2(MAXN - 1);
    for(int i = 0; i < testTime; ++i)
    {
        // 生成随机数据进行验证
        int n = rand() % MAXN;
        if(divisors1(n) != d[n]) cout << "出错了！" << endl;
    }

    return 0;
}